1. Field
The present disclosure relates to a mobile operating environment, and more particularly, to distributed networks and methods and apparatus for multiple keyword queries, such as AND and OR queries, on a distributed network.
2. Background
An overlay network is a virtual network of nodes and logical links that is built on top of an existing network. Examples of an overlay network include, but are not limited to, the Internet, Chord, Content Addressable Network (CAN), Pastry, and Viceroy. In some overlay networks, each node can store a portion of overlay network data, called a partition, so as to distribute the data across the network to increase network efficiency in storage and retrieval of the data.
A device or node that joins an overlay network may desire to obtain a service from another device or node in the overlay network. Such services are published in the overlay network using any one of a plurality of service description languages, each having a corresponding service discovery protocol for use to find the published service. A definition of service discovery as given by Wikipedia states: “[s]ervice discovery protocols are network protocols which allow automatic detection of devices and services offered by these devices on a computer network.” In other words, service discovery is the action of finding a service provider for a requested service. When the location of the demanded service (typically the address of the service provider) is retrieved, the user may further access and use it.
In general, service discovery protocols include two entities: (a) the service provider—who provides the service on the overlay, and (b) the client—who uses the service. In one aspect, examples of a service provider include nodes which provide services such as printing, scanning, faxing, storage, music share, file share, games, and web services such as for booking movie tickets, hotels, air tickets, or online gaming, etc. Further, any node in the network can act as a client. Thus, the goal of service discovery is to help the client find a service provider for a particular service of interest (if such a service exists).
For service discovery to be successful in a peer-to-peer overlay network, the service provider should specify its service(s) using a service description language, metadata about the service should be stored in some searchable form on nodes in the overlay, and clients should be able to express the service requests using searchable keywords that are passed on to the querying system to help find the corresponding services.
As part of the publication process, keywords are extracted from the service description document and separately published in a distributed manner over the distributed network. Queries can then be issued by individual nodes to discover keywords and/or services. Typically, performing a search for two or more keywords involves conducting an AND search wherein a query is sent to each node including one of the keywords. Similarly, an OR search is performed by sending a query to each node that includes one or more of the multiple keywords forming the query. Such typical searches are associated with a high communication cost.
Thus, it would be desirable to have a method of handling multiple keyword queries more efficiently and with an optimized communication cost.